package test;

import java.util.Scanner;

public class WangYi1 {

    static int NINF = Integer.MIN_VALUE / 3;
    static Integer[][] memo;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        for (int i = 0; i < num; i++) {
            int length = scanner.nextInt();
            int[] arr = new int[length];
            for (int j = 0; j < length; j++) {
                arr[j] = scanner.nextInt();
            }
            System.out.println(tallestBillboard(arr));
        }
    }
    public static int tallestBillboard(int[] rods) {
        int N = rods.length;
        memo = new Integer[N][10001];
        int maxHight = dp(rods, 0, 5000);
        int sum = 0;
        for (int i = 0; i < rods.length; i++) {
            sum += rods[i];
        }
        return sum - 2 * maxHight;
    }

    public static int dp(int[] rods, int i, int s) {
        if (i == rods.length) {
            return s == 5000 ? 0 : NINF;
        } else if (memo[i][s] != null) {
            return memo[i][s];
        } else {
            int ans = dp(rods, i+1, s);
            ans = Math.max(ans, dp(rods, i+1, s-rods[i]));
            ans = Math.max(ans, rods[i] + dp(rods, i+1, s+rods[i]));
            memo[i][s] = ans;
            return ans;
        }
    }
}
